#include <stdio.h>
#include <stdlib.h>
#include "Traversal.h"

//递归前序遍历
void preOrderTraversal(TreeNode* root){
    if(root == NULL) return;

    printf("%c",root->data);
    preOrderTraversal(root->left);
    preOrderTraversal(root->right);
}

//递归中序遍历
void inOrderTraversal(TreeNode* root){
    if(root == NULL) return;

    inOrderTraversal(root->left);
    printf("%c",root->data);
    inOrderTraversal(root->right);
}

//递归后序遍历
void postOrderTraversal(TreeNode* root){
    if(root == NULL) return;

    postOrderTraversal(root->left);
    postOrderTraversal(root->right);
    printf("%c",root->data);
}

//层序遍历(使用队列) （都是先赋值再运算）
void levelOrderTraversal(TreeNode* root){
    if(root == NULL) return;

    //创建队列
    TreeNode* queue[100];
    int front = 0, rear = 0;

    //一进
    queue[rear++] = root;

    while(front < rear){
        //二出
        TreeNode* current = queue[front++];
        printf("%c", current->data);

        //三扩
        if(current->left != NULL){
            queue[rear++] = current->left;
        }
        
        if(current->right != NULL){
            queue[rear++] = current->right;
        }
    }

}

//非递归前序遍历
void preOrderIterative(TreeNode* root){
    if(root == NULL) return;

    //创建栈
    TreeNode* stack[100];
    int top = -1;

    //一进（与层序遍历不同，进的时候先加再赋值，因为一开始top=-1）
    stack[++top] = root;

    while(top >= 0){
        //二出
        TreeNode* current = stack[top--];    //弹出栈顶节点（先赋值再减）
        printf("%c", current);               //访问弹出的节点

        //三扩（先右后左入栈，保证出栈顺序为左→右）
        if(current->right != NULL){
            stack[++top] = current->right;
        }

        if(current->left != NULL){
            stack[++top] = current->left;
        }
    }
}

//非递归中序遍历
void inorderIterative(TreeNode* root){
    //先判断是否为空树
    if(root == NULL) return;

    //创建栈
    TreeNode* stack[100];
    int top = -1;
    TreeNode* current = root;

    //当前节点非空 或者 栈非空 才执行
    while(current != NULL || top >= 0){

        //一进。根节点先进，再一直入左子树节点
        while(current != NULL){
            stack[++top] = current;
            current = current->left;
        }

        //二出。上面的循环结束，说明该节点为最左端节点，所以该节点节点出栈
        current = stack[top--];
        printf("%c", current);

        //三扩右。
        //有右节点：一进再二出，弹出右节点
        //无右节点：继续二出
        current = current->right;
    }
    /*
    中序遍历的核心是“​​先压栈根节点和所有左子节点，再访问当前节点，最后处理右子树​​”，
    右节点的处理也完全遵循这一规则，
    其入栈和弹出均服务于“左→根→右”的顺序。
    在我的代码注释里面，只有A才是根节点。（最顶部那个）
    */
}

//非递归后序遍历
void postorderIterative(TreeNode* root){
    //先判断是否为空树
    if(root == NULL) return 0;

    //创建两个栈
    TreeNode* stack1[100];   //辅助栈2，用于控制遍历顺序
    TreeNode* stack2[100];   //在栈1的帮助下，栈2从顶部到底部的节点顺序为左右根
    int top1 = -1, top2 = -1;

    stack1[++top1] = root;  // 根节点入栈1

    while (top1 >= 0) {  // 遍历栈1
        TreeNode* current = stack1[top1--];  // 弹出栈1顶节点（顺序为根→右→左）
        stack2[++top2] = current;  // 将节点压入栈2（顺序为根→右→左）

        // 栈1的入栈顺序：先左后右（保证栈2的出栈顺序为左→右→根）
        if (current->left != NULL) {
            stack1[++top1] = current->left;  // 左子节点入栈1
        }
        if (current->right != NULL) {
            stack1[++top1] = current->right;  // 右子节点入栈1
        }
    }

    // 栈2中的节点顺序是「根→右→左」，逆序输出即为后序遍历（左→右→根）
    while (top2 >= 0) {
        printf("%c ", stack2[top2--]->data);  // 从栈顶到栈底输出
    }
}